Mathematical induction

Mathematical induction is a method for proving that a statement is true for every natural number, that is, that the infinitely many cases all hold. Informal metaphors help to explain this technique, such as falling dominoes or climbing a ladder.

A proof by induction consists of two cases. The first, the base case, proves the statement for without assuming any knowledge of other cases. The second case, the induction step, proves that if the statement holds for any given case , then it must also hold for the next case .

In other words

What we are doing is proving that if the statement works for ANY of the numbers, it will work for the next one. In the induction step we are NOT proving that the statement works for a number. Instead we are proving that IF we have a number that the statement works for, it will work for the next.

Example:

Base step

For

Induction step

For :
Is it true that for ,
We've already assumed that is true and is also true so must be true.
Mathematical induction exercises > 2)

Complete/Strong induction

Strong induction differentiates itself from weak induction by assuming that the statement is true for all values before n.

Mathematical induction exercises > 4)Fibonacci

Example

#todo add example